import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.AbstractMap;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.Scanner;
import java.util.Set;
import javax.swing.JTextArea;

public class TextGraphProcessor {
    // 图的数据结构
    private Map<String, Set<Edge>> graph = new HashMap<>();
    private String inputFileName;

    // 边类
    static class Edge {
        String source;
        String target;
        int weight;

        public Edge(String source, String target, int weight) {
            this.source = source;
            this.target = target;
            this.weight = weight;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Edge edge = (Edge) o;
            return Objects.equals(source, edge.source) && Objects.equals(target, edge.target);
        }

        @Override
        public int hashCode() {
            return Objects.hash(source, target);
        }
    }

    public TextGraphProcessor(String inputFileName) {
        this.inputFileName = inputFileName;
    }

    // 获取图结构
    public Map<String, Set<Edge>> getGraph() {
        return graph;
    }

    // 主方法
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String fileName;

        // 允许用户选择或输入文件名
        System.out.println("请输入文本文件路径：");
        fileName = scanner.nextLine();

        TextGraphProcessor processor = new TextGraphProcessor(fileName);

        try {
            // 读取文本并生成有向图
            processor.readTextAndBuildGraph();

            // 显示菜单，允许用户选择功能
            boolean running = true;
            while (running) {
                System.out.println("\n请选择功能：");
                System.out.println("1. 显示有向图");
                System.out.println("2. 查询桥接词");
                System.out.println("3. 根据桥接词生成新文本");
                System.out.println("4. 计算两个单词之间的最短路径");
                System.out.println("5. 计算PageRank值");
                System.out.println("6. 随机游走");
                System.out.println("0. 退出");

                int choice = scanner.nextInt();
                scanner.nextLine(); // 清除换行符

                switch (choice) {
                    case 1:
                        processor.showDirectedGraph();
                        break;
                    case 2:
                        System.out.println("请输入第一个单词：");
                        String word1 = scanner.nextLine().toLowerCase();
                        System.out.println("请输入第二个单词：");
                        String word2 = scanner.nextLine().toLowerCase();
                        String result = processor.queryBridgeWords(word1, word2);
                        System.out.println(result);
                        break;
                    case 3:
                        System.out.println("请输入文本：");
                        String inputText = scanner.nextLine();
                        String newText = processor.generateNewText(inputText);
                        System.out.println("生成的新文本：" + newText);
                        break;
                    case 4:
                        System.out.println("请输入第一个单词：");
                        word1 = scanner.nextLine().toLowerCase();
                        System.out.println("请输入第二个单词：");
                        word2 = scanner.nextLine().toLowerCase();
                        String path = processor.calcShortestPath(word1, word2);
                        System.out.println(path);
                        break;
                    case 5:
                        System.out.println("请输入要计算PageRank的单词：");
                        String word = scanner.nextLine().toLowerCase();
                        double pr = processor.calPageRank(word);
                        System.out.println(word + "的PageRank值为：" + pr);
                        break;
                    case 6:
                        String walkResult = processor.randomWalk();
                        System.out.println("随机游走结果：\n" + walkResult);
                        break;
                    case 0:
                        running = false;
                        break;
                    default:
                        System.out.println("无效选择，请重试。");
                }
            }
        } catch (IOException e) {
            System.err.println("读取文件错误: " + e.getMessage());
        }

        scanner.close();
    }

    // 读取文本并生成有向图
    public void readTextAndBuildGraph() throws IOException {
        BufferedReader reader = new BufferedReader(new FileReader(inputFileName));
        String line;
        List<String> words = new ArrayList<>();

        // 读取所有文本行
        while ((line = reader.readLine()) != null) {
            // 将文本转换为小写并替换所有非字母为空格
            line = line.toLowerCase().replaceAll("[^a-z]", " ");
            // 分割单词并添加到列表中
            String[] lineWords = line.trim().split("\\s+");
            for (String word : lineWords) {
                if (!word.isEmpty()) {
                    words.add(word);
                }
            }
        }
        reader.close();

        // 构建有向图
        for (int i = 0; i < words.size() - 1; i++) {
            String current = words.get(i);
            String next = words.get(i + 1);

            if (!graph.containsKey(current)) {
                graph.put(current, new HashSet<>());
            }

            // 检查是否已存在这条边
            boolean edgeExists = false;
            for (Edge edge : graph.get(current)) {
                if (edge.target.equals(next)) {
                    edge.weight++;
                    edgeExists = true;
                    break;
                }
            }

            // 如果边不存在，添加新边
            if (!edgeExists) {
                graph.get(current).add(new Edge(current, next, 1));
            }

            // 确保目标单词也作为一个节点存在于图中
            if (!graph.containsKey(next)) {
                graph.put(next, new HashSet<>());
            }
        }
    }

    // 显示有向图 (控制台版本)
    public void showDirectedGraph() {
        System.out.println("有向图的边：");
        for (String source : graph.keySet()) {
            for (Edge edge : graph.get(source)) {
                System.out.println(source + " -> " + edge.target + " (权重: " + edge.weight + ")");
            }
        }
    }

    // 显示有向图 (GUI版本)
    public void showDirectedGraph(JTextArea textArea) {
        textArea.append("有向图的边：\n");
        for (String source : graph.keySet()) {
            for (Edge edge : graph.get(source)) {
                textArea.append(source + " -> " + edge.target + " (权重: " + edge.weight + ")\n");
            }
        }
    }

    // 查询桥接词
    public String queryBridgeWords(String word1, String word2) {
        if (!graph.containsKey(word1) || !graph.containsKey(word2)) {
            return "No " + word1 + " or " + word2 + " in the graph!";
        }

        List<String> bridges = new ArrayList<>();

        // 查找所有从word1出发的边
        for (Edge edge1 : graph.get(word1)) {
            String bridge = edge1.target;
            // 查找从bridge出发到word2的边
            if (graph.containsKey(bridge)) {
                for (Edge edge2 : graph.get(bridge)) {
                    if (edge2.target.equals(word2)) {
                        bridges.add(bridge);
                        break;
                    }
                }
            }
        }

        if (bridges.isEmpty()) {
            return "No bridge words from \"" + word1 + "\" to \"" + word2 + "\"!";
        } else {
            StringBuilder result = new StringBuilder("The bridge words from \"" + word1 + "\" to \"" + word2 + "\" are: ");
            for (int i = 0; i < bridges.size(); i++) {
                result.append("\"").append(bridges.get(i)).append("\"");
                if (i < bridges.size() - 1) {
                    result.append(", ");
                }
                if (i == bridges.size() - 2) {
                    result.append("and ");
                }
            }
            return result.toString();
        }
    }

    // 根据桥接词生成新文本
    public String generateNewText(String inputText) {
        if (inputText == null || inputText.trim().isEmpty()) {
            return "";
        }

        // 清洗输入：转小写、保留空格，将非字母替换为空格
        inputText = inputText.toLowerCase().replaceAll("[^a-z]", " ").trim();

        if (inputText.isEmpty()) {
            return "";
        }

        String[] words = inputText.split("\\s+");
        if (words.length <= 1) {
            return inputText;  // 只剩一个词或为空，直接返回清洗后的 inputText
        }

        StringBuilder result = new StringBuilder();
        result.append(words[0]);

        for (int i = 0; i < words.length - 1; i++) {
            String current = words[i];
            String next = words[i + 1];

            // 查找桥接词
            String bridgeResult = queryBridgeWords(current, next);
            if (!bridgeResult.startsWith("No")) {
                String[] parts = bridgeResult.split("are: ");
                if (parts.length > 1) {
                    String bridgesStr = parts[1].replaceAll("\"", "");
                    String[] bridges = bridgesStr.split(", |and ");

                    if (bridges.length > 0) {
                        Random random = new Random();
                        String selectedBridge = bridges[random.nextInt(bridges.length)];
                        result.append(" ").append(selectedBridge);
                    }
                }
            }

            result.append(" ").append(next);
        }

        return result.toString();
    }


    // 计算两个单词之间的最短路径
    public String calcShortestPath(String word1, String word2) {
        boolean word1Exists = graph.containsKey(word1);
        boolean word2Exists = graph.containsKey(word2);

        if (!word1Exists) {
            // 起点不存在，返回词不存在
            return "No " + word1 + " or " + word2 + " in the graph!";
        }

        // 如果两个词相同，直接返回距离0
        if (word1.equals(word2)) {
            return "The shortest path from \"" + word1 + "\" to \"" + word2 + "\" is: " + word1 + " (距离: 0)";
        }

        // 如果终点不存在，返回无路径
        if (!word2Exists) {
            return "No path from \"" + word1 + "\" to \"" + word2 + "\"!";
        }

        // 使用Dijkstra算法计算最短路径
        Map<String, Integer> distances = new HashMap<>();
        Map<String, String> previous = new HashMap<>();
        PriorityQueue<Map.Entry<String, Integer>> queue = new PriorityQueue<>(
                Comparator.comparingInt(Map.Entry::getValue));
        Set<String> visited = new HashSet<>();

        for (String node : graph.keySet()) {
            distances.put(node, Integer.MAX_VALUE);
        }
        distances.put(word1, 0);
        queue.add(new AbstractMap.SimpleEntry<>(word1, 0));

        while (!queue.isEmpty()) {
            String current = queue.poll().getKey();

            if (current.equals(word2)) {
                break;
            }

            if (visited.contains(current)) {
                continue;
            }

            visited.add(current);

            for (Edge edge : graph.get(current)) {
                String neighbor = edge.target;
                int newDist = distances.get(current) + edge.weight;

                if (newDist < distances.getOrDefault(neighbor, Integer.MAX_VALUE)) {
                    distances.put(neighbor, newDist);
                    previous.put(neighbor, current);
                    queue.add(new AbstractMap.SimpleEntry<>(neighbor, newDist));
                }
            }
        }

        if (distances.get(word2) == Integer.MAX_VALUE) {
            return "No path from \"" + word1 + "\" to \"" + word2 + "\"!";
        }

        List<String> path = new ArrayList<>();
        String current = word2;
        while (current != null) {
            path.add(current);
            current = previous.get(current);
        }
        Collections.reverse(path);

        StringBuilder result = new StringBuilder("The shortest path from \"" + word1 + "\" to \"" + word2 + "\" is: ");
        for (int i = 0; i < path.size(); i++) {
            result.append(path.get(i));
            if (i < path.size() - 1) {
                result.append(" -> ");
            }
        }
        result.append(" (距离: ").append(distances.get(word2)).append(")");

        return result.toString();
    }

    // 计算PageRank值
    public double calPageRank(String word) {
        if (!graph.containsKey(word)) {
            return 0.0;
        }

        int nodeCount = graph.keySet().size();
        double d = 0.85;
        Map<String, Double> ranks = new HashMap<>();
        Map<String, Double> newRanks = new HashMap<>();

        // 初始化 PR
        for (String node : graph.keySet()) {
            ranks.put(node, 1.0 / nodeCount);
        }

        // 迭代计算
        for (int i = 0; i < 10; i++) {
            // 每轮新值清空
            for (String node : graph.keySet()) {
                newRanks.put(node, 0.0);
            }

            // 遍历每个节点
            for (String source : graph.keySet()) {
                double pr = ranks.get(source);
                int outDegree = graph.get(source).size();

                if (outDegree == 0) {
                    // 出度为 0，均匀分发
                    double distributed = pr / nodeCount;
                    for (String node : graph.keySet()) {
                        newRanks.put(node, newRanks.get(node) + distributed);
                    }
                } else {
                    // 正常分发给出边指向的节点
                    for (Edge edge : graph.get(source)) {
                        String target = edge.target;
                        newRanks.put(target, newRanks.get(target) + pr / outDegree);
                    }
                }
            }

            // 应用阻尼因子
            for (String node : graph.keySet()) {
                double rank = newRanks.get(node);
                rank = (1.0 - d) / nodeCount + d * rank;
                newRanks.put(node, rank);
            }

            // 更新 ranks
            ranks = new HashMap<>(newRanks);
        }

        return ranks.get(word);
    }


    // 随机游走
    public String randomWalk() {
        if (graph.isEmpty()) {
            return "图为空，无法进行随机游走";
        }

        // 随机选择一个起始节点
        Random random = new Random();
        List<String> nodes = new ArrayList<>(graph.keySet());
        String current = nodes.get(random.nextInt(nodes.size()));

        StringBuilder path = new StringBuilder(current);
        Set<String> visitedEdges = new HashSet<>();

        while (true) {
            // 获取当前节点的所有出边
            Set<Edge> edges = graph.get(current);
            if (edges.isEmpty()) {
                break; // 如果没有出边，结束游走
            }

            // 转换为列表以便随机选择
            List<Edge> edgeList = new ArrayList<>(edges);
            Edge selectedEdge = edgeList.get(random.nextInt(edgeList.size()));

            // 构造边的唯一标识符
            String edgeId = selectedEdge.source + "->" + selectedEdge.target;

            // 如果边已经访问过，结束游走
            if (visitedEdges.contains(edgeId)) {
                break;
            }

            visitedEdges.add(edgeId);
            current = selectedEdge.target;
            path.append(" ").append(current);
        }

        return path.toString();
    }
}